package de.uni_saarland.coli.doclists.suffixtree;

import java.util.List;

import de.uni_saarland.coli.doclists.document.IndexDocument;
import de.uni_saarland.coli.doclists.index.Index;

/**
 * 
 * @author stefan
 * 
 *         Searches a suffix in the suffix tree.
 */
public class TreeSearch {

	/**
	 * current pos in the suffix
	 */
	private int currentPos;

	/**
	 * the suffix
	 */
	private List<Integer> suffix;

	/**
	 * Constructor.
	 */
	public TreeSearch() {
		this.currentPos = 0;
		this.suffix = null;
	}

	/**
	 * Returns an edge or null
	 * 
	 * @param node
	 *            the start node.
	 * @param token
	 *            the token.
	 * @return the edge or null
	 */
	private STreeEdge findEdge(int node, int token) {
		return Index.getEdgeMap().find(node, token);
	}

	/**
	 * Returns the next node. iterates over the suffix if the edge is size > 1
	 * 
	 * @param edge
	 *            the edge
	 * @return the node or null is not matching
	 */
	private STreeNode findNextNode(STreeEdge edge) {
		if (edge == null)
			return null;

		if (edge.getFirstTokenIndex() + 1 == edge.getLastTokenIndex()) {
			// only one character along the edge
			return Index.getNodeMap().getNode(edge.getEndNode());
		} else {
			// multiple character along the edge

			IndexDocument refenceDoc = Index.getDocumentManager().getDocument(
					edge.getBaseDocID());

			// compare characters of the edge starting with the second
			// first chracter already checked and
			// currentPos should match second character of the edge
			// checks until last edge character or last suffix character

			for (int i = edge.getFirstTokenIndex(); i < edge
					.getLastTokenIndex()
					&& this.currentPos < this.suffix.size(); i++) {
				// no matching == now node reachable
				if (refenceDoc.getTermAt(i) != this.suffix.get(this.currentPos))
					return null;

				this.currentPos++;
			}
			// contained in edge
			return Index.getNodeMap().getNode(edge.getEndNode());
		}
	}

	/**
	 * Returns the end node of a suffix or null.
	 * 
	 * @param suffix
	 *            the suffix
	 * @return the node or null
	 */
	public STreeNode find(List<Integer> suffix) {
		this.currentPos = 0;
		this.suffix = suffix;
		STreeEdge currentEdge = this.findEdge(0, this.suffix.get(0));

		// no edge from the root
		if (currentEdge == null)
			return null;

		if (currentEdge.getFirstTokenIndex() + 1 == currentEdge
				.getLastTokenIndex())
			this.currentPos++;

		STreeNode currentNode = Index.getNodeMap().getNode(
				currentEdge.getEndNode());

		while (this.currentPos < suffix.size()) {
			// next node
			currentNode = this.findNextNode(currentEdge);
			// no node found
			if (currentNode == null)
				return null;

			// end of suffix reached and node found
			if (this.currentPos >= suffix.size())
				return currentNode;

			currentEdge = this.findEdge(currentNode.getNodeID(),
					this.suffix.get(this.currentPos));
			
			if (currentEdge == null)
				return null;
			
			if (currentEdge.getFirstTokenIndex() + 1 == currentEdge
					.getLastTokenIndex())
				this.currentPos++;

		}

		return currentNode;
	}
}
